Nowadays individual products are tagged with transponders or transponder chips which have various functions. For instance, in a shop they are used as ID tags or price tags to simplify the inventory, shipping/distribution process, while at home they may be used by various devices (refrigerator, washing machine) to electronically identify products or properties of products, respectively. As an example: a washing machine may warn the user, if she/he wants to wash clothing with a washing program which may damage the clothing.
One example of such a transponder is a so-called Radio Frequency Identification tag, or RFID tag for short. The terms RFID tag and transponder, as used herein, comprise data carriers containing information that can be read out by reading devices in a contactless manner. The information carried by the RFID tag comprises electronic product codes (EPC) but also product information, like the type of product, price, where it is supposed to go, etc. Further, RFID tags can also contain information for the user, like the washing temperature, handling process of the product, use/by date before which the product should be used, etc.
RFID tags are small, often bendable, tags. They normally consist of a small IC plus an antenna. The typical size of the IC is about 1 mm2, while the antenna can be much larger. RFID tags generally have no power supply of their own (battery or similar), but respond to an electromagnetic field generated by a reading device. When being within such an electromagnetic field they gain electric power from this field, and are able to receive messages and give responses. However, the invention is not limited to passive transponders but also related to active transponders.
RFID tags are very widely used. Examples are: animal identification tags, access keys to doors, suitcase handling at airports, supply chain management, inventory management, etc. RFID tags are furthermore operable in various frequency ranges, reaching from low frequency up to the microwave band.
RFID tags are low-power devices, but nevertheless are gaining more and more capabilities. They are able to do calculations and may contain a working processor. An RFID tag may comprise several types of memory, like NV-RAM (non-volatile RAM) which is only active when electric power is present, a ROM part which can be written once and is thereafter unchangeable, an erasable ROM (EROM) which can be written and erased multiple times, etc.
Of course, it is most convenient and cost effective for a manufacturer (or a shop keeper) to put as many functions as possible in a single RFID tag. However, while the use of RFID tags is convenient and practical, it could be a bad thing if an RFID tag can be read out by unauthorized third parties, because this results in a violation of privacy. For example, detection of RFID tagged medicine for treating AIDS or impotence, “embarrassing” items, like sex articles, or expensive jewelry or other (less visible) valuable items (marking the wearer as target for robberies) could be awkward or even dangerous for the affected persons, if such information falls into the wrong hands.
Generally, an RFID tag will send out a fixed message which is stored in some type of memory, which takes no calculation time for preparing the message. The fixed messages may contain plain character strings and/or statically encrypted strings. However, when a tag sends out the exact same message all the time, then security problems with linkability and tracking arise, regardless of whether this message is encrypted or not. In this document “linkability” is a term used to describe that a transponder (and the product to which it is fixed) is assignable to a specific person, when the transponder transmits the same message all the time. Even though the RFID tag does not transmit directly person-related information like “I am owned by Alice”, an attacker can recognize Alice by this RFID tag transmitting the same message every time, once he finds an instance enabling him to assign (“link”) this message to Alice. Linkability can be hindered by semantically secure encryption of the messages transmitted by the RFID tag, requiring that the re-encryption has to be carried out every time when the message is read out. “Tracking” is the term used for exactly this: Alice is linked to a transponder and can be tracked by an attacker by following the transponder. Tracking may even be possible when semantically secure encryption is used, but the key used for it has leaked.
In order to overcome these privacy problems inherent in RFID tags several approaches are conceivable:                The RFID tag is destroyed or disabled or removed from the product once it has fulfilled its inventory task or the like in a shop or warehouse, etc. This approach has the disadvantage that the RFID tag is no longer useable for later applications, like in-home use.        The message transmission speed of the RFID is set to be so low that an unauthorized reader has not enough time and means to read the tag en passant (when passing by). This is undesirable, as authorized readers want to be able to read the tag rapidly.        
Document US 2004/0222878 A1 describes the use of cryptographic techniques having a complexity level which permits their implementation in an inexpensive RFID tag. In an RFID system comprising one or more transponders and at least one reader that communicates with the devices, a plurality of pseudonyms is associated with a given one of the transponders. The transponder transmits different ones of the pseudonyms in response to different reader queries, and an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same transponder. For additional security it is proposed in this document to impose a low query response rate within the transponder, which may be accomplished by implementing hardware-based response delays within the transponder. In another example it is suggested to specify a maximum rate at which the transponder is permitted to respond to reader queries with transmitted pseudonyms.
The known transponder systems, however, suffer from the disadvantage that when the suggested query response throttling measures are implemented within the transponders transmitting the pseudonyms from the transponders to the readers will always be accomplished at reduced response rates and will thereby limit the applicability of the transponder system to low-speed applications. A further disadvantage of the known transponder system is that keeping track of all the pseudonyms requires a lot of administration.